/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ssp.strategy.agent;

import ssp.strategy.agent.util.DijkstraTable;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.logging.Level;
import ssp.agent.QualityDemand;
import ssp.database.DatabaseManager;
import ssp.database.NetworkMap;
import ssp.database.ServiceMap;
import ssp.event.DepartureEvent;
import ssp.event.EventQueue;
import ssp.net.NWcomponent;
import ssp.net.NWcomponentManager;
import ssp.service.FrontendServer;
import ssp.topology.Node;
import ssp.utility.LoggingManager;
import ssp.utility.MapValueAscending;
import ssp.utility.Pair;
import ssp.utility.PropertyManager;

/**
 * Agent_v1クラスのStrategyを実際に実現したクラス<br>
 * 提案手法であるEnhanced Fallback+を実装している
 * @author yamazaki
 */
public final class Agent_v1_Strategy_v1 extends Agent_v1_Strategy {
    
    @Override
    public List<FrontendServer> searchFrontendServer(QualityDemand qualityDemand, NWcomponent belongingNWcomponent, int hopNum, int chargeNum) {
        
        //ユーザが属するネットワークコンポーネントからNホップ以内のフロントエンドサーバを全て取得
        List<FrontendServer> frontendServersFromNetworkMap = new ArrayList<>(DatabaseManager.getINSTANCE().getNetworkMap().getNearbyServer(belongingNWcomponent.getID(), hopNum));
        
        //サービスマップから取得したフロントエンドサーバのIDと残り容量の逆数を保持するためのリスト
        Map<Integer, Double> frontendServersFromServiceMap = new TreeMap<>();
        
        ServiceMap svMap = DatabaseManager.getINSTANCE().getServiceMap();
        for(int frontednServerID : DatabaseManager.getINSTANCE().getServiceMap().getFrontendServierList(qualityDemand.getTypeID())) {
            if(svMap.getAvailability(frontednServerID) < svMap.getWorkload(new Pair<>(frontednServerID, qualityDemand.getTypeID())) + PropertyManager.getValueAsDouble("FrontendServerMargin")) {
                continue;
            }
            boolean qosFlg = true;
            int qosNum = qualityDemand.getServiceQualityList().size();
            for(int i=0 ; i<qosNum ; i++) {
                if(svMap.getQosIndex(new Pair<>(frontednServerID, qualityDemand.getTypeID()), i) < qualityDemand.getServiceQualityList().get(i)) {
                    qosFlg = false;
                    break;
                }
            }
            if(qosFlg) {
                frontendServersFromServiceMap.put(frontednServerID, svMap.getRecipAvailability(frontednServerID));
            }
        }
        
        TreeMap<Integer, Double> recipAvailabilityMap = new TreeMap<>(new MapValueAscending(frontendServersFromServiceMap));
        recipAvailabilityMap.putAll(frontendServersFromServiceMap);
        
        List<Integer> newList = new ArrayList<>();
        for(int i=0 ; i<chargeNum ; i++) {
            if(recipAvailabilityMap.isEmpty()) {
                break;
            }
            newList.add(recipAvailabilityMap.pollFirstEntry().getKey());
        }
                
        LoggingManager.logging(Level.FINEST, "The size of frontendServerFromNetworkMap: " + frontendServersFromNetworkMap.size(), new Throwable());
        LoggingManager.logging(Level.FINEST, "The size of frontendServerFromServiceMap: " + frontendServersFromServiceMap.size(), new Throwable());
        
        List<FrontendServer> intersection = new ArrayList<>();
        
        //2つのリストから共通するフロントエンドサーバを抽出
        for(int id : newList) {
            for(FrontendServer frontendServer : frontendServersFromNetworkMap) {
                if(id == frontendServer.getID()) {
                    intersection.add(frontendServer);
                }
            }
        }
        
//        //2つのリストから共通するフロントエンドサーバを抽出
//        for(FrontendServer frontendServer : frontendServersFromNetworkMap) {
//            if(newList.contains(frontendServer.getID())) {
//                intersection.add(frontendServer);
//            }
//        }
        
        return intersection;
    }
    
    @Override
    public Pair<FrontendServer, List<NWcomponent>> searchPath(QualityDemand demand, NWcomponent belongingNWcomponent, FrontendServer frontendServer) {
        
        //宛先ノード
        NWcomponent dstNode = (NWcomponent)frontendServer.getConnectedNWcomponent();
        
        //1週目は料金，それ以降はQoSindexに注目
        for(int i=-1 ; i<demand.getNetworkQualityList().size() ; i++) {
            
            //注目した指標に基づいたDijkstra
            List<DijkstraTable> tableList = dijkstraStar(belongingNWcomponent, dstNode, i, demand);
            
            if(tableList == null) {
                return null;
            }
            
            //料金以外の注目指標で
            if(i >= 0) {
                
                //最短路が要求を満たしていなければ次の指標へ
                if(tableList.get(i+1).getResultCost() > demand.getNetworkQualityList().get(i)) {
                    continue;
                }
            }
            
            boolean flg = true;
            
            //注目指標以外の指標でresultCostが要求を満たしていないものがあればdstNodeの手前までの最短路を探索
            for (int j=0 ; j<demand.getNetworkQualityList().size() ; j++) {
                if(i != j && tableList.get(j+1).getResultCost() > demand.getNetworkQualityList().get(j)) {
                    flg = false;
                }
            }
            if(!flg) {
                List<NWcomponent> path = backtarceToNeighbor(belongingNWcomponent, tableList, demand, i);
                if (path.isEmpty()) {
                    continue;
                } else {
                    return new Pair<>(frontendServer, path);
                }
            }
            
            //各候補経路を確認
            for(int tableNum=0 ; tableNum<tableList.size() ; tableNum++) {
                flg = true;
                List<Integer> path = tableList.get(tableNum).bachwardTrace();
                
                //各指標を満たせているか否かを確認
                for(int j=0 ; j<demand.getNetworkQualityList().size() ; j++) {
                    double sum = 0;
                    int prevNode = -1;
                    int currentNode = -1;
                    for(int nodeID : path) {
                        if(prevNode == -1) {
                            prevNode = nodeID;
                            continue;
                        } else if(currentNode == -1) {
                            currentNode = nodeID;
                            sum += (int)tableList.get(j+1).getCost(currentNode);
                            continue;
                        } else {
                            Set<Node> connectedNode = new HashSet<>();
                            connectedNode.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(prevNode));
                            connectedNode.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(nodeID));
                            Pair<Integer, Set<Node>> key = new Pair<>(currentNode, connectedNode);
                            sum += DatabaseManager.getINSTANCE().getNetworkMap().getQoSindex(key, j);
                            prevNode = currentNode;
                            currentNode = nodeID;
                        }
                    }
                    if(demand.getNetworkQualityList().get(j) < sum) {
                        flg = false;
                        break;
                    }
                }
                
                //満たせていればreturn
                if(flg) {
                    List<NWcomponent> resultPath = new ArrayList<>();
                    for(int id : path) {
                        resultPath.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(id));
                    }
                    return new Pair<>(frontendServer, resultPath);
                }
            }
            
            //全ての候補が要求を満たせないならdstNodeの手前までの最短路を探索
            List<NWcomponent> path = backtarceToNeighbor(belongingNWcomponent, tableList, demand, i);
            if(path.size() > 0) {
                return new Pair<>(frontendServer, path);
            }
        }
        
        //要求を満たすものが発見できなければnullを返す
        return null;
    }
    
    @Override
    public boolean makeService(FrontendServer frontendServer, List<NWcomponent> nwComponents, QualityDemand demand) {
        
        //利用料金
        double charge = 0.0;
        
        //フロントエンドサーバに到着できなければfalse
        if(!frontendServer.arrival(frontendServer.getServiceEntry(demand.getTypeID()))) {
            return false;
        }
        
        charge += frontendServer.getServiceEntry(demand.getTypeID()).getCharge();
        
        //ネットワークコンポーネントへ到着できなければ解放してfalse
        NWcomponent prevNode = null;
        NWcomponent currentNode = null;
        NWcomponent nextNode = null;
        for(NWcomponent node : nwComponents) {
            if(prevNode == null) {
                prevNode = node;
            } else if(currentNode == null) {
                currentNode = node;
                charge += prevNode.getNWresourceManager().getCharge(node, prevNode.getEndsOfInternalPath(node), demand.getBandwidth(), demand.getServiceTimeLength());
                if(!prevNode.getNWresourceManager().reserveResources(node, prevNode.getEndsOfInternalPath(node), demand.getBandwidth())) {
                    return false;
                }
            } else {
                nextNode = node;
                if(!currentNode.getNWresourceManager().reserveResources(prevNode, nextNode, demand.getBandwidth())) {
                    
                    //到着できない場合はこれまでのリソースを解放
                    NWcomponent n_prevNode = null;
                    NWcomponent n_currentNode= null;
                    for(NWcomponent n_node : nwComponents) {
                        if(n_prevNode == null) {
                            n_prevNode = n_node;
                        } else if(n_currentNode == null) {
                            n_currentNode = n_node;
                        } else {
                            n_currentNode.getNWresourceManager().releaseResources(n_prevNode, n_node, demand.getBandwidth());
                            n_prevNode = n_currentNode;
                            n_currentNode = n_node;
                            if(nextNode.equals(n_node)) {
                                break;
                            }
                        }
                    }
                    return false;
                }
                charge += currentNode.getNWresourceManager().getCharge(prevNode, nextNode, demand.getBandwidth(), demand.getServiceTimeLength());
                
                prevNode = currentNode;
                currentNode = nextNode;
            }
        }
        
        //ログ用
        StringBuilder path = new StringBuilder(50);
        
        for(NWcomponent node : nwComponents) {
            path.append(node.getID());
            path.append(", ");
        }
        
//        LoggingManager.logging(Level.INFO, "FrontendServer: " + frontendServer.getID() + ", path: " + path + " charge: " + charge + " is reserved.", new Throwable());
        if(EventQueue.getINSTANCE().isIsLogging())
            LoggingManager.logging(Level.INFO, "FrontendServer: " + frontendServer.getID() + ", path: " + path + " charge: " + charge + " is reserved.", null);

        //予約できれば退去イベントをキューに追加してtrue
        EventQueue eventQueue = EventQueue.getINSTANCE();
        eventQueue.addEvent(new DepartureEvent(eventQueue.getCurrentTime() + demand.getServiceTimeLength(), frontendServer, nwComponents, demand));
        
        return true;
    }
    
    /**
     * Enhanced Fallback+のための拡張Dijkstra
     * @param srcNode 源ノード
     * @param dstNode 宛先ノード
     * @param index 注目するQoS指標
     * @param demand QualityDemand
     * @return 結果
     */
    private List<DijkstraTable> dijkstraStar(NWcomponent srcNode, NWcomponent dstNode, int index, QualityDemand demand) {
        List<DijkstraTable> result = new ArrayList<>();
        List<Integer> closed = new ArrayList<>();
        
        NetworkMap NWDB = DatabaseManager.getINSTANCE().getNetworkMap();
        
        for(int i=0 ; i<=demand.getNetworkQualityList().size() ; i++) {
            result.add(i, new DijkstraTable(dstNode.getID()));
            result.get(i).put(-1, srcNode.getID(), 0);
        }
        
        //initialize step
        for(Node nextNode : srcNode.getNeighborNWcomponents()) {
            double cost;
            Set<Node> connectedNode = new HashSet<>();
            connectedNode.add(nextNode);
            connectedNode.add(srcNode.getEndsOfInternalPath((NWcomponent)nextNode));
            Pair key = new Pair(srcNode.getID(), connectedNode);
            if(NWDB.getAvailability(key) < (demand.getBandwidth() / NWDB.getBandwidthUnit(key)) + PropertyManager.getValueAsDouble("NetworkComponentMargin")) {
                continue;
            }
            for(int i=-1 ; i< demand.getNetworkQualityList().size() ; i++) {
                if(i == -1) {
                    cost = NWDB.getRecipAvailability(key);
                } else {
                    cost = NWDB.getQoSindex(key, i);
                }
                result.get(i+1).put(srcNode.getID(), ((NWcomponent)nextNode).getID(), cost);
            }
        }
        closed.add(srcNode.getID());
        
        int currentNodeID = result.get(index+1).getNextNode(srcNode.getID(), closed);
        if(currentNodeID == -1) {
            return null;
        }
        closed.add(currentNodeID);
        
        // loop step
        Set<Node> connectedNode = new HashSet<>();
        while (true) {
            for (Node nextNode : NWDB.getConnectionList(currentNodeID)) {
                NWcomponent next = (NWcomponent) nextNode;
                if(!closed.contains(next.getID())) {
                        connectedNode.clear();
                        connectedNode.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(result.get(index+1).getPrevNode(currentNodeID)));
                        connectedNode.add(nextNode);
                        Pair<Integer, Set<Node>> key = new Pair<>(currentNodeID, connectedNode);
                        
                        // 空き容量が無いものは選択しない
                        if(NWDB.getAvailability(key) < (demand.getBandwidth() / NWDB.getBandwidthUnit(key)) + PropertyManager.getValueAsDouble("NetworkComponentMargin")) {
                            continue;
                        }
                        
                        if(next.getID() == result.get(index+1).getDstNodeID()) {
                            Set<Node> connecNode_ = new HashSet<>();
                            Node currentNode_ = NWcomponentManager.getINSTANCE().getNWcomponentFromID(currentNodeID);
                            connecNode_.add(currentNode_);
                            connecNode_.add(((NWcomponent)nextNode).getEndsOfInternalPath((NWcomponent)currentNode_));
                            Pair<Integer, Set<Node>> key_ = new Pair(((NWcomponent)nextNode).getID(), connecNode_);
                            if(NWDB.getAvailability(key_) < (demand.getBandwidth() / NWDB.getBandwidthUnit(key_)) + PropertyManager.getValueAsDouble("NetworkComponentMargin")) {
                                continue;
                            }
                        }
                        
                        for(int i=-1 ; i<demand.getNetworkQualityList().size() ; i++) {
                        //↓隣接ホップの重み
                        double weight;
                        if(i == -1) {
                            weight = NWDB.getRecipAvailability(key);
                            //weight = NWDB.getCharge(key, demand.getBandwidth());
                        } else {
                            weight = NWDB.getQoSindex(key, i);
                        }

                        if(result.get(i + 1).getCost(currentNodeID) + weight < result.get(i + 1).getCost(next.getID())) {
                            //更新
                            result.get(i + 1).put(currentNodeID, next.getID(), result.get(i + 1).getCost(currentNodeID) + weight);
                        }
                    }
                }
                connectedNode.clear();
            }
            currentNodeID = result.get(index+1).getNextNode(currentNodeID, closed);
            closed.add(currentNodeID);
            if(currentNodeID == -1) {
                break;
            }
        }
        return new ArrayList<>(result);
    }
    
    /**
     * dijkstraStarのためのバックトレースステップ
     * @param srcNode
     * @param resultTable
     * @param demand
     * @param index
     * @return 
     */
    private List<NWcomponent> backtarceToNeighbor(NWcomponent srcNode, List<DijkstraTable> resultTable, QualityDemand demand, int index) {
        NWcomponent dstNode = NWcomponentManager.getINSTANCE().getNWcomponentFromID(resultTable.get(index+1).getDstNodeID());
        for(Node neighbor : dstNode.getNeighborNWcomponents()) {
            boolean flg = true;
            List<Integer> path = new ArrayList<>();
            try {
                path = new ArrayList<>(resultTable.get(index+1).backwardTrace(((NWcomponent)neighbor).getID()));
            } catch(NullPointerException e) {
                continue;
            }
            for(int i=0 ; i<demand.getNetworkQualityList().size() ; i++) {
                if(path.size() == 1) {
                    continue;
                }
                double cost = resultTable.get(i+1).getCost(path.get(1));
                int prevNode = -1;
                int currentNode = -1;
                int nextNode = -1;
                for(int node : path) {
                    if(node == srcNode.getID()) {
                        prevNode = node;
                        continue;
                    } else if (resultTable.get(index+1).getPrevNode(node) == srcNode.getID()) {
                        currentNode = node;
                        continue;
                    } else {
                        nextNode = node;
                        Set<Node> connectedNodes = new HashSet<>();
                        connectedNodes.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(prevNode));
                        connectedNodes.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(nextNode));
                        Pair<Integer, Set<Node>> key = new Pair<>(currentNode, connectedNodes);
                        cost += DatabaseManager.getINSTANCE().getNetworkMap().getQoSindex(key, i);
                        prevNode = currentNode;
                        currentNode = nextNode;
                    }
                }
                
                if(demand.getNetworkQualityList().get(i) < cost) {
                    flg = false;
                    break;
                }
            }
            if(flg) {
                path.add(resultTable.get(index+1).getDstNodeID());
                List<NWcomponent> resultPath = new ArrayList<>();
                for(int id : path) {
                    resultPath.add(NWcomponentManager.getINSTANCE().getNWcomponentFromID(id));
                }
                return resultPath;
            }
        }
        return new ArrayList<>();
    }

    @Override
    public String toString() {
        StringBuilder buffer = new StringBuilder(50);
        buffer.append("[");
        buffer.append(new Throwable().getStackTrace()[0].getClassName());
        buffer.append("]");
        return buffer.toString();
    }
    
}
